package com.jiang.专题.动态规划.Q740;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/23 22:25
 */
class Solution {
    // 动态规划
    // public int deleteAndEarn(int[] nums) {
    //     int maxValue = 0;
    //     for (int num: nums) {
    //         maxValue = Math.max(maxValue, num);
    //     }
    //     int[] sum = new int[maxValue + 1];
    //     for (int num: nums) {
    //         sum[num] += num;
    //     }
    //     return rob(sum);
    // }

    // public int rob(int[] sum) {
    //     int size = sum.length;
    //     int first = sum[0], second = Math.max(sum[0], sum[1]);
    //     for (int i = 2; i < size; i++) {
    //         int temp = second;
    //         second = Math.max(first + sum[i], second);
    //         first = temp;
    //     }
    //     return second;
    // }

    // 排序 + 动态规划
    public int deleteAndEarn(int[] nums) {
        int res = 0;
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        list.add(nums[0]);
        int size = 1;
        for (int i = 1; i < nums.length; i++) {
            int diff = nums[i] - nums[i - 1];
            if (diff == 0) {
                list.set(size - 1, list.get(size - 1) + nums[i]);
            } else if (diff == 1) {
                list.add(nums[i]);
                size++;
            } else {
                res += rob(list);
                list.clear();
                list.add(nums[i]);
                size = 1;
            }
        }
        res += rob(list);
        return res;
    }

    public int rob(List<Integer> list) {
        int size = list.size();
        if (size == 1)
            return list.get(0);
        int l = list.get(0), r = Math.max(l, list.get(1));
        for (int i = 2; i < size; i++) {
            int temp = r;
            r = Math.max(r, l + list.get(i));
            l = temp;
        }
        return r;
    }
}
